import java.util.Hashtable;
import java.util.LinkedList;
import java.util.Queue;

/**
 * 
 * @author Amr
 */
public class SimpleControl {
	private Hashtable<String, State[]> transitionTable;
	private int childrenNum;
	private Queue<SimpleNode> queue;
	private Hashtable<String, String> history; 
	/**
	 * The constructor of the class.
	 */
	public SimpleControl(Hashtable<String,State[]> newTransiHashtable, int newChildrenNum) {
		transitionTable = newTransiHashtable;
		childrenNum=newChildrenNum;
		queue=new LinkedList<SimpleNode>();
		history=new Hashtable<String, String>();
	}
	/**
	 * get the next node, put it as one of the current node children.
	 * @param node, current input
	 * @return child node.
	 */
	private SimpleNode getNextNode(SimpleNode currentNode, int input) {
		String childState=transitionTable.get(currentNode.getValue())[input].getState();
		currentNode.setChild(new SimpleNode(currentNode,childState,input+"",childrenNum),input);
		return currentNode.getChild(input);
	}
	/**
	 * check for rule two to find if the specified node was found before or not.
	 * @param node to apply rule one on it.
	 * @return true if found before 
	 */
	private boolean checkRuleTwo(SimpleNode node){
		if(!history.isEmpty()&&history.contains(node.getValue())){
			return true;
		}else{
			history.put(node.getValue(), node.getValue());
			return false;
		}
	}
	/**
	 * check for rule one to find if the specified node was the target node or not.
	 * @param node to apply rule one on it.
	 * @return true if the specified node was the required one.
	 */
	private boolean checkRuleOne(SimpleNode node,SimpleNode targetNode){
		if(node.getValue()==targetNode.getValue()){
			getSequence(node);
			return true;
		}else{
			return false;
		}
	}
	/**
	 * create the sequence for the required node.
	 * @param node
	 * @return sequence for the node.
	 */
	private String getSequence(SimpleNode node){
		String seq="";
		String type="I";
		if(childrenNum>2){
			type="I";
		}
		while(node.getParent()!=null){
			seq=type+node.getGivenInput()+" "+seq;
			node=node.getParent();
		}
		System.out.println("The sequence: "+seq);
		return seq;
	}
	/**
	 * build the full simple tree.
	 * @param initialValue
	 * @param finalValue
	 */
	public void buildSimpleControlTree(String initialValue,String finalValue){
		SimpleNode initialNode=new SimpleNode(null, initialValue, "", childrenNum);
		SimpleNode finalNode=new SimpleNode(null, finalValue, "", childrenNum);
		queue.add(initialNode);
		
		while(queue.size()>0){
			SimpleNode node=queue.poll();
			if(!checkRuleTwo(node)&&!checkRuleOne(node,finalNode)){
				for (int i = 0; i < childrenNum; i++) {
					SimpleNode n=getNextNode(node, i);
					queue.add(n);
				}
			}
		}
	}
	/**
	 * 
	 * Main
	 */
	public static void main(String[] args) {
		int childrenPerNode=2;
		Hashtable<String, State[]> transitionTable = new Hashtable<String, State[]>();
		
		//exaple1:
//		State[] A = { new State("C", "0"), new State("E", "0") };
//		State[] B = { new State("A", "0"), new State("D", "0") };
//		State[] C = { new State("E", "1"), new State("D", "0") };
//		State[] D = { new State("F", "1"), new State("A", "0") };
//		State[] E = { new State("B", "1"), new State("F", "0") };
//		State[] F = { new State("B", "1"), new State("C", "0") };
//		transitionTable.put("A", A);
//		transitionTable.put("B", B);
//		transitionTable.put("C", C);
//		transitionTable.put("D", D);
//		transitionTable.put("E", E);
//		transitionTable.put("F", F);
		
		//exaple2:
		State[] A = { new State("B", "0"), new State("D", "0") };
		State[] B = { new State("A", "0"), new State("B", "0") };
		State[] C = { new State("D", "1"), new State("A", "0") };
		State[] D = { new State("D", "1"), new State("C", "0") };
		transitionTable.put("A", A);
		transitionTable.put("B", B);
		transitionTable.put("C", C);
		transitionTable.put("D", D);

		
		SimpleNode node = new SimpleNode(null,"B",null,childrenPerNode);
		SimpleControl sim = new SimpleControl(transitionTable,childrenPerNode);
		sim.buildSimpleControlTree("A", "C");
	}

}
